package backtrack;

/**
 * @author : Rookie
 * @description : 24点
 * @date : 2023/6/23
 */
public class TwentyFourHours {

    private static final double EPSILON = 1e-6; // 定义误差范围

    private static boolean solve24(int[] nums) {
        // 当 nums 只包含一个数字且等于 24 时，返回 true
        if (nums.length == 1 && Math.abs(nums[0] - 24) < EPSILON) {
            return true;
        }
        // 生成nums中所有可能组合
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                int a = nums[i];
                int b = nums[j];

                // 将剩余元素拷贝到一个新数组中
                int[] newNums = new int[nums.length - 1];
                int m = 0;
                for (int k = 0; k < nums.length; k++) {
                    if (k !=i && k !=j) {
                        newNums[m++] = nums[k];
                    }
                }

                // 进行四则运算
                // 加法
                newNums[m] = a+b;
                if (solve24(newNums)) {
                    return true;
                }
                // 减法
                // a-b
                newNums[m] = a-b;
                if (solve24(newNums)) {
                    return true;
                }
                // b-a
                newNums[m] = b-a;
                if (solve24(newNums)) {
                    return true;
                }
                // 乘法
                newNums[m] = a*b;
                if (solve24(newNums)) {
                    return true;
                }

                // 除法
                // a/b
                if (Math.abs(b) > EPSILON) {
                    newNums[m] = a/b;
                    if (solve24(newNums)) {
                        return true;
                    }
                }
                // b/a
                if (Math.abs(a) > EPSILON) {
                    newNums[m] = b/a;
                    if (solve24(newNums)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] set = {7, 2, 1, 10};
        boolean solve24 = solve24(set);
        System.out.println("是否能组成24点：" + solve24);
    }
}
